package cn.lishiyuan.algorithm.strings;

/**
 * Rabin-Karp 算法
 */
public class BKMatcher implements Matcher{

    private final static long base = 257;

    private final static long mod = 1000000007;

    @Override
    public boolean match(CharSequence source, CharSequence word) {
        return find(source,word) != -1;
    }

    @Override
    public int find(CharSequence source, CharSequence word) {

        // codePoints或者chars
        int[] sourceArray = source.chars().toArray();
        int[] wordsArray = word.chars().toArray();

        int wordsArrayLength = wordsArray.length;
        int sourceArrayLength = sourceArray.length;

        if (sourceArrayLength < wordsArrayLength){
            return -1;
        }

        if (wordsArrayLength == 0){
            return -1;
        }

        int index = -1;
        long[] pow = basePow(wordsArrayLength-1);
        long wordHash = hash(wordsArray,0,wordsArrayLength,0,pow);
        long oldHash = 0;

        for (int i = 0; i < sourceArrayLength - wordsArrayLength + 1; i++){

            // 循环
            long hash = hash(sourceArray,i,wordsArrayLength,oldHash,pow);
            if (wordHash == hash){
                boolean match = true;
                for (int j = 0; j < wordsArrayLength; j++) {
                    if (wordsArray[j] != sourceArray[i+j]){
                        match = false;
                        break;
                    }
                }
                if(match){
                    index = i;
                    break;
                }
            }

            oldHash = hash;
        }

        return index;
    }

    private long[] basePow(int n){
        long[] pow = new long[n + 1];
        pow[0] = 1;
        for (int i = 1; i <= n; i++) {
            // 每一步都取模防止溢出
            pow[i] = (pow[i - 1] * base) % mod; // 预计算模mod的幂次
        }
        return pow;
    }


    // 滚动hash
    private long hash(int[] arr, int start, int length, long hash, long[] pow) {
        // 初始化时计算哈希
        if (hash == 0) {
            long h = 0;
            for (int i = 0; i < length; i++) {
                // 每一步都取模防止溢出
                h = (h + (long) arr[start + i] * pow[length - 1 - i]) % mod; // 权重从高位到低位
            }
            return h;
        } else {
            // 移除首字符影响，添加新字符
            // 每一步都取模防止溢出
            long remove = (arr[start - 1] * pow[length - 1]) % mod;
            long add = arr[start + length - 1] % mod;
            hash = (hash - remove) % mod;
            hash = (hash * base + add) % mod;

            return hash < 0 ? hash + mod : hash; // 确保非负
        }
    }

}
